package com.sali.双指针;

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 */
public class LeetCode_76 {

    public String minWindow(String s, String t) {
        int[] charDic = new int[128];

        for (char ch : t.toCharArray()) {
            charDic[ch] += 1;
        }

        int resLen = Integer.MAX_VALUE;
        int start = 0;
        int left = 0;
        int targetLen = t.length();

        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            if (charDic[ch] > 0) {
                targetLen -= 1;
            }
            charDic[ch] -= 1;
            if (targetLen != 0) {
                continue;
            }
            while (charDic[s.charAt(left)] < 0 && left < right) {
                charDic[s.charAt(left)] += 1;
                left++;
            }
            if (resLen > right - left + 1) {
                resLen = right - left + 1;
                start = left;
            }
            charDic[s.charAt(left)] += 1;
            left++;
            targetLen++;
        }

        return resLen == Integer.MAX_VALUE ? "" : s.substring(start, start + resLen);
    }

}
